GermanWikipedia - /page/entry.mu

<!DOCTYPE html>

<title>Shellsort</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading">Shellsort</h1>

</header>

</div>

Shellsort ist ein von <a href="Donald_L._Shell" title="Donald L. Shell">Donald L. Shell</a> im Jahr 1959 entwickeltes <a href="Sortierverfahren" title="Sortierverfahren">Sortierverfahren</a>, das auf dem Sortierverfahren des direkten Einfügens (<a href="Insertionsort" title="Insertionsort">Insertionsort</a>) basiert.

<div class="mw-heading mw-heading2"><h2 id="Prinzip">Prinzip</h2></div>

Der Grundgedanke besteht darin, die unsortierte <a href="Folge_(Mathematik)" title="Folge (Mathematik)">Folge</a> so umzuordnen, dass man eine sortierte <a href="Teilfolge" title="Teilfolge">Teilfolge</a> enthält, wenn man jedes h-te Element entnimmt. Das soll für jedes beliebige Anfangsfeld gelten.<a href="#cite_note-1">[1]</a>

Der Algorithmus von Shellsort setzt diese Idee um, indem er die unsortierte Folge in mehrere Teilfolgen aufteilt und danach die Einträge innerhalb jeder Teilfolge sortiert. Beispielsweise führt eine Aufteilung in 4 Teilfolgen zu einer Teilfolge mit den Indizes 0, 4, 8, …, einer anderen mit den Indizes 1, 5, 9, … und so weiter. Nach einem solchen Sortierschritt nennt man die Folge 4-sortiert.

Shellsort führt mehrere Sortierschritte mit unterschiedlichen Abständen aus. Der erste Sortierschritt erzeugt die meisten Teilfolgen, also auch den größten Abstand zwischen den Indizes einer Teilfolge. Der Abstand wird mit jedem Schritt kleiner. Wenn z. B. Shellsort mit Abstand 4 anfängt, dann wird die Folge erst 4-sortiert, dann 2-sortiert, und zuletzt mit normalem Insertionsort sozusagen 1-sortiert.

Anschaulich ist dies anhand von Hilfsmatrizen darzustellen (siehe Beispiel):

<ul><li>Die Daten werden zeilenweise in eine h-spaltige <a href="Matrix_(Mathematik)" title="Matrix (Mathematik)">Matrix</a> geschrieben</li>

<li>Die Spalten der Matrix werden einzeln sortiert</li></ul>

Daraus resultiert eine grobe Sortierung. Dieser Schritt wird mehrmals wiederholt, wobei jeweils die Breite der Matrix verringert wird, bis die Matrix nur noch aus einer einzigen vollständig sortierten Spalte besteht.

Eine a*b-sortierte Sequenz ist nicht auch automatisch a-sortiert oder b-sortiert. Zum Beweis betrachten wir eine Sequenz aus den Zahlen 1 bis 12. Diese ist 6-sortiert, wenn wir auf eine beliebige <a href="Permutation" title="Permutation">Permutation</a> der Zahlen 1, 2, 3, 4, 5, 6 eine ebenfalls beliebige Permutation der Zahlen 7, 8, 9, 10, 11, 12 folgen lassen. Die Permutation 6, 5, 4, 3, 2, 1 ist nicht 2- oder 3-sortiert. Daher ist 6, 5, 4, 3, 2, 1, 7, 8, 9, 10, 11, 12 zwar 6-sortiert, aber nicht 2- und auch nicht 3-sortiert.

Shellsort arbeitet <a href="In-place-Algorithmus" title="In-place-Algorithmus">in-place</a>, gehört jedoch nicht zu den <a href="Stabilit%C3%A4t_(Sortierverfahren)" title="Stabilität (Sortierverfahren)">stabilen</a> <a href="Sortierverfahren" title="Sortierverfahren">Sortieralgorithmen</a>. Aufgrund der Sortierung über Distanz verliert die Sortiermethode ihre Eigenschaft „stabil“. Zwei benachbarte gleichwertige Elemente werden verschiedenen Untersequenzen zugeordnet und final möglicherweise so sortiert, dass ihre ursprüngliche Reihenfolge vertauscht wird.

<div class="mw-heading mw-heading2"><h2 id="Beispiel">Beispiel</h2></div>

Zu sortieren sind die Zahlen 2, 5, 3, 4, 3, 9, 3, 2, 5, 4, 1, 3 mittels der Abstandsfolge <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1,2,4,...2^{n}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1,2,4,...2^{n}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7c35637982af4dae6767d67afd842d30446db172.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:11.685ex; height:2.676ex;" alt="{\displaystyle 1,2,4,...2^{n}}" loading="lazy">.

Zuerst werden die Daten zeilenweise in eine Matrix mit vier (größtes Element der Abstandsfolge, das kleiner ist als die Hälfte der Länge der zu sortierenden Sequenz) Spalten eingetragen und spaltenweise sortiert. Die Zahlenfolge wird also 4-sortiert.

<pre>2 5 3 4 2 4 1 2

3 9 3 2 → 3 5 3 3

5 4 1 3 5 9 3 4

</pre>

Die sortierte Vier-Spalten-Matrix wird nun in zwei Spalten aufgeteilt, wobei von links nach rechts gelesen wird. Diese Spalten werden nun 2-sortiert.

<pre>2 4 1 2

1 2 2 3

3 5 → 3 4

3 3 3 4

5 9 3 5

3 4 5 9

</pre>

Die sortierte Zwei-Spalten-Matrix wird nun in eine Zeile geschrieben und wieder sortiert mittels normalem Insertionsort. Der Vorteil dabei besteht darin, dass jetzt kein Element der Sequenz mehr so weit verschoben werden muss wie beim Insertionsort allein, der ja auf eine nicht vorsortierte Folge angewendet wird.

<pre>1 2 2 3 3 4 3 4 3 5 5 9 → 1 2 2 3 3 3 3 4 4 5 5 9

</pre>

Die hier verwendete Abstandsfolge <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1,2,4,...2^{n}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1,2,4,...2^{n}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7c35637982af4dae6767d67afd842d30446db172.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:11.685ex; height:2.676ex;" alt="{\displaystyle 1,2,4,...2^{n}}" loading="lazy"> (wie es 1959 original von Shell vorgeschlagen wurde) erweist sich in der Praxis allerdings als nicht zweckmäßig, da nur gerade Stellen sortiert werden und ungerade Stellen der Sequenz nur im letzten Schritt angefasst werden. Als zweckmäßiger hat sich 1, 4, 13, 40 … erwiesen (Wertn = 3×Wertn-1+1).

<div class="mw-heading mw-heading2"><h2 id="Implementierung">Implementierung</h2></div>

Shellsort ist eine Verbesserung des Algorithmus Insertionsort. Dort wandern nämlich die Elemente in Einzelschritten auf ihren Platz: Nach dem Finden des kleinsten Elements werden die dazwischenliegenden einzeln hochgeschoben und nur das kleinste „springt“. Die meisten (d. h. n) Elemente werden von ihrem ursprünglichen Platz in durchschnittlich n/3 Schritten zu ihrem endgültigen Platz geschoben.

Beim Shell-Sort führt man abnehmende Schrittweiten k[1], k[2] … k[t] ein, wobei die letzte Schrittweite immer k[t] = 1 ist. Es werden nacheinander t Schritte durchgeführt; im m-ten Schritt springen die Elemente in Richtung ihres zukünftigen Platzes um jeweils k[m] Stellen. Im ersten Schritt werden diejenigen Elemente untereinander sortiert, die k[1] Stellen voneinander entfernt sind; dann diejenigen, die eine Entfernung k[2] voneinander haben usw. Der Effekt dieser Vorgehensweise ist es, dass die Elemente im ersten Durchgang nicht um einen, sondern um k[1] Stellen zu ihrem Platz „springen“.

Die letzte Schrittweite k[t] ist 1, d. h. zum Schluss wird ein ganz normaler Sortiervorgang straight insertion durchgeführt. Dies garantiert, dass am Ende die Reihung sortiert ist. Der Algorithmus braucht jedoch kaum noch etwas zu tun, da die vorherigen Schritte die Reihung schon fast vollständig sortiert haben.

Durch die geeignete Wahl der Schrittweiten k[1], k[2] … k[t] kann der Sortieraufwand deutlich reduziert werden. Für die Schrittweiten (1, 3, 7, 15, 31 …) wurde nachgewiesen (s. <a href="Donald_E._Knuth" title="Donald E. Knuth">Donald E. Knuth</a>: <a href="The_Art_of_Computer_Programming" title="The Art of Computer Programming">The Art of Computer Programming</a>), dass die Zeitkomplexität des Algorithmus n1,5 beträgt, was deutlich besser ist als die quadratische Komplexität von <a href="Bubblesort" title="Bubblesort">Bubblesort</a>, Insertionsort oder <a href="Selectionsort" title="Selectionsort">Selectionsort</a>, jedoch (zumindest für sehr große Datenmengen) schlechter als die Komplexität n log n von <a href="Mergesort" title="Mergesort">Mergesort</a> oder <a href="Heapsort" title="Heapsort">Heapsort</a>.

<div class="mw-highlight mw-highlight-lang-java mw-content-ltr" dir="ltr"><pre> static <E extends Comparable<? super E>> void shellSort(E[] sammlung, int[] schrittweiten) {

for (int schrittweite : schrittweiten) { // straight insertion mit schrittweite

for (int index = schrittweite; index < sammlung.length; index++){

E elementZumEinfuegen = sammlung[index];

int einfuegestelle = index;

while (einfuegestelle - schrittweite >= 0 &&

elementZumEinfuegen.compareTo(sammlung[einfuegestelle-schrittweite]) < 0) {

sammlung[einfuegestelle] = sammlung[einfuegestelle - schrittweite];

einfuegestelle -= schrittweite; // Sprung um schrittweite

}

sammlung[einfuegestelle] = elementZumEinfuegen;

}

</pre></div>

Tatsächlich sind die Daten nicht in Form einer Matrix, sondern in Form eines eindimensionalen Feldes angeordnet. Die Spalten einer Matrix werden durch geschickte Indizierung gebildet. So bilden alle Elemente in einem gegebenen Abstand h eine Spalte. Die Spalten werden per Insertionsort sortiert, da dieser Algorithmus von einer Vorsortierung der Daten profitieren kann.

In folgendem Programm werden die Daten zuerst in h=2147483647 Spalten angeordnet, sofern so viele Daten vorhanden sind. Wenn nicht, wird die for-i-Schleife übersprungen und mit h=1131376761 fortgefahren usw.

<div class="mw-highlight mw-highlight-lang-java mw-content-ltr" dir="ltr"><pre>void shellsort (int[] a, int n)

{

int i, j, k, h, t;

int[] spalten = {2147483647, 1131376761, 410151271, 157840433,

58548857, 21521774, 8810089, 3501671, 1355339, 543749, 213331,

84801, 27901, 11969, 4711, 1968, 815, 271, 111, 41, 13, 4, 1};

for (k = 0; k < spalten.length; k++)

{

h = spalten[k];

// Sortiere die "Spalten" mit Insertionsort

for (i = h; i < n; i++)

{

t = a[i];

j = i;

while (j >= h && a[j-h] > t)

{

a[j] = a[j-h];

j = j - h;

}

a[j] = t;

}

}

</pre></div>

<div class="mw-heading mw-heading2"><h2 id="Komplexität_und_Distanzfolgen">Komplexität und Distanzfolgen</h2></div>

Die Komplexität von Shellsort hängt von der Wahl der Distanzfolge für die Spaltenanzahl h ab. Für verschiedene Folgen sind Obergrenzen der Komplexität bewiesen worden, die damit einen Anhaltspunkt für die Laufzeit geben. Die meisten theoretischen Arbeiten über die Folgen betrachten nur die Anzahl der Vergleiche als wesentlichen Kostenfaktor. Doch in realen Implementierungen zeigt sich, dass auch die Schleifen und Kopieraktionen bei nicht riesigen Arrays eine entscheidende Rolle spielen.

Ursprünglich schlug Donald Shell die Folge 1, 2, 4, 8, 16, 32 …, 2k vor. Die Performance ist allerdings sehr schlecht, weil erst im allerletzten Schritt die Elemente auf ungeraden Positionen sortiert werden. Die Komplexität ist mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Theta (n^{2})}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (n^{2})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/215877752c4f392a7276328d4d37709bf7c3f55d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.066ex; height:3.176ex;" alt="{\displaystyle \Theta (n^{2})}" loading="lazy"> sehr hoch.

Mit der Folge 1, 3, 7, 15, 31, 63 …, 2k - 1 von Hibbard wird eine Komplexität von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(n^{1,5})}">

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(n^{1,5})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2cdc518373ac71b69b834e9395f3d0c8c3e7464c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.388ex; height:3.176ex;" alt="{\displaystyle {\mathcal {O}}(n^{1,5})}" loading="lazy"> erreicht.

Mit der Folge 1, 2, 3, 4, 6, 8, 9, 12, 16 …, 2p3q von Pratt beträgt die Komplexität <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(n\cdot \log(n)^{2})}">

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(n\cdot \log(n)^{2})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7725a6381c8a9a15a2330278e652832375998f95.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.963ex; height:3.176ex;" alt="{\displaystyle {\mathcal {O}}(n\cdot \log(n)^{2})}" loading="lazy">.

<a href="Donald_E._Knuth" title="Donald E. Knuth">Donald E. Knuth</a> hat auch einige Folgen für Shellsort erarbeitet. Eine häufig in der Literatur verwendete ist folgende: 1, 4, 13, 40, 121, 364, 1093 …, (3k-1)/2. Bekannter ist die Berechnungsvorschrift derselben Folge: 3hk-1 + 1. Die Komplexität ist <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(n^{1,5})}">

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(n^{1,5})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2cdc518373ac71b69b834e9395f3d0c8c3e7464c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.388ex; height:3.176ex;" alt="{\displaystyle {\mathcal {O}}(n^{1,5})}" loading="lazy">.

Einige gute Folgen stammen von <a href="Robert_Sedgewick_(Informatiker)" title="Robert Sedgewick (Informatiker)">Robert Sedgewick</a>.

Die Folge 1, 8, 23, 77, 281, 1073, 4193, 16577 …, 4k+1 + 3*2k + 1 hat Komplexität von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(n^{4/3})}">

</mrow>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(n^{4/3})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ba1c8acaacc82d0a1cea7ab996e72f05ce4c2194.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.752ex; height:3.343ex;" alt="{\displaystyle {\mathcal {O}}(n^{4/3})}" loading="lazy"> erreicht.

Eine wesentlich bessere Folge ist folgende: 1, 5, 19, 41, 109, 209, 505, 929, 2161, 3905, 8929, 16001 …, 9*2k - 9*2k/2 + 1 (k gerade) bzw. 8*2k - 6*2(k+1)/2 + 1 (k ungerade).

Betrachtet man rein geometrische Folgen, so liegt ein Minimum der Laufzeit in der größeren Umgebung von Faktor 2,3, d. h. die Folgeglieder haben das Verhältnis von ungefähr 2,3. Eine der theoretisch besten Folgen (d. h. Zahl der Vergleiche), die experimentell von Marcin Ciura ermittelt wurde, ist 1, 4, 10, 23, 57, 132, 301, 701, 1750 und basiert auf diesem Faktor. Basierend auf dem Faktor 1750/701 wird die Reihe wie folgt fortgesetzt: Sei g das letzte Glied, dann ist das nächste durch 1+floor(2,5*g) gegeben, also 701, 1753, 4383, 10958, 27396, 68491, 171228, …

Eine Folge von Gonnet und Baeza-Yates basiert auf dem Faktor 2,2, die sehr gute Ergebnisse liefert.

Erstaunlicherweise sind in der Praxis bessere Folgen als die von Marcin Ciura bekannt, die sich rekursiv berechnen. Die Laufzeit des Shellsort ist kürzer, obwohl die Zahl der Vergleiche höher ist (zu sortierende Elemente sind Ganzzahlen in Registerbreite). Rekursive Folgen berechnen sich aus Ganzzahlen, und das Verhältnis der Folgeglieder konvergiert gegen einen bestimmten Wert, bei den Fibonaccizahlen ist es der <a href="Goldener_Schnitt" title="Goldener Schnitt">Goldene Schnitt</a>.

Eine solche Folge basiert auf den <a href="Fibonacci-Folge" title="Fibonacci-Folge">Fibonaccizahlen</a>. Eine der beiden 1er am Anfang wird weggelassen und jede Zahl der Folge mit dem Doppelten des <a href="Goldener_Schnitt" title="Goldener Schnitt">Goldenen Schnitts</a> (ca. 3,236) potenziert, was dann zu dieser Distanzfolge führt: 1, 9, 34, 182, 836, 4025, 19001, 90358, 428481, 2034035 …

Eine andere rekursive Folge wurde von Matthias Fuchs gefunden. Die Folge 1, 4, 13, 40, 124, 385, 1195, 3709, 11512, 35731 … hat als Konvergenzwert ungefähr 3.103803402. Die Berechnungsvorschrift ist fk+1 = 3*fk + fk-2, wobei die Folge initial mit 1, 1, 1 startet und für den Shellsort die ersten beiden 1er weggelassen werden.

Andere Folgen sind nicht konstant, sondern werden aus der aktuellen Anzahl von Elementen im Array berechnet. Initialisiert werden sie mit dieser Anzahl und sinken ab, bis sie schließlich bei 1 angekommen sind:

<ul><li>Robert Kruse: hk-1 = hk/3 + 1</li>

<li>Gonnet und Baeza-Yates: hk-1 = (5*hk - 1) / 11</li></ul>

Beide Folgen haben eine etwas schlechtere Performance als die beiden rekursiven Folgen und die sehr gute Folgen von Sedgewick und die von Marcin Ciura. Aber sie sind direkt in den Shellsort-Algorithmus integrierbar.

Die Existenz einer Folge mit der Komplexität <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(n\cdot \log(n))}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(n\cdot \log(n))}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/41addf5ff9fad19fe3a34d951c6ada35738b171f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.909ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(n\cdot \log(n))}" loading="lazy"> wurde bereits ausgeschlossen in einer Arbeit von <a href="Bjorn_Poonen" title="Bjorn Poonen">Bjorn Poonen</a>, Plaxton, und Suel<a href="#cite_note-2">[2]</a>. Doch konnte bewiesen werden, dass prinzipiell für hinreichend großes n immer eine Folge mit einer Komplexität von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(n^{1+\varepsilon })}">

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(n^{1+\varepsilon })}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/28d6372ba88a49e6e0aec3fd9b6db6a1f8575088.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.153ex; height:3.176ex;" alt="{\displaystyle {\mathcal {O}}(n^{1+\varepsilon })}" loading="lazy"> gefunden werden kann.

Die Suche nach einer optimalen Folge gestaltet sich dabei als äußerst schwierig. Zu große Abstände zwischen den Folgegliedern ergeben zu große Verschiebungen, zu enge Abstände bewirken zu viele Durchläufe bis zur letztendlichen Sortierung. Dabei gilt es bei der Wahl einer Folge zu vermeiden, dass zwei aufeinanderfolgende Glieder der Folge gemeinsame Teiler haben, da eine a*b-Sortierung und eine anschließende a*c-Sortierung bestimmte Unterfolgen von der Sortierung ausschließt (vgl. Anmerkung zur ursprünglichen Folge 1, 2, 4, 8, 16 …, die die ungeraden auslässt und erst bei der 1-Sortierung berücksichtigt). Über mehrere Glieder hinweg ist das durchaus von Vorteil.

Ein wesentlicher Vorteil des Shellsort-Algorithmus im Vergleich zu anderen liegt darin, dass er bereits vorhandene Sortierungen ausnutzen kann. Dabei spielt es nur eine geringe Rolle, ob das Array sortiert oder invers sortiert vorliegt. Beide Fälle sind um Faktoren schneller als ein rein zufällig sortiertes Array. Bei nur 65536 Elementen beträgt der Geschwindigkeitsvorteil ca. Faktor 4, bei 128 immerhin noch mehr als Faktor 2.

<a href="Insertionsort" title="Insertionsort">Insertionsort</a> ist langsam, weil nur benachbarte Elemente ausgetauscht werden. Wenn sich zum Beispiel das kleinste Element zufällig am Ende des Feldes befindet, dann braucht der Algorithmus n Schritte, um es an den Anfang zu schieben. Shellsort ist eine einfache Erweiterung von Insertionsort, die die Effizienz dadurch erhöht, dass sie auch Elemente vertauscht, die weit voneinander entfernt sind.<a href="#cite_note-3">[3]</a>

<div class="mw-heading mw-heading2"><h2 id="Variationen">Variationen</h2></div>

<a href="Combsort" title="Combsort">Combsort</a> arbeitet ähnlich wie Shellsort. Dabei wird die Spaltensortierung mit nur einem Durchlauf von <a href="Bubblesort" title="Bubblesort">Bubblesort</a> sortiert, bevor die Spaltenanzahl verringert wird.

<div class="mw-heading mw-heading2"><h2 id="Literatur">Literatur</h2></div>

<ul><li><a href="Donald_L._Shell" title="Donald L. Shell">Donald L. Shell</a>: A High-Speed Sorting Procedure. In: Timon N. Commun. ACM, 2(7), 1959, S. 30–32.</li>

<li><a href="Robert_Sedgewick_(Informatiker)" title="Robert Sedgewick (Informatiker)">Robert Sedgewick</a>: Algorithms in Java, Part 1–4. Addison-Wesley, ISBN 0-201-36120-5.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Weblinks">Weblinks</h2></div>

<div class="sisterproject" style="margin:0.1em 0 0 0;"><div class="noviewer" style="display:inline-block; line-height:10px; min-width:1.6em; text-align:center;" aria-hidden="true" role="presentation"></div><a href="https://de.wikibooks.org/wiki/Algorithmen_und_Datenstrukturen_in_C/_Shellsort" class="extiw external" title="b:Algorithmen und Datenstrukturen in C/ Shellsort">Wikibooks: Algorithmen und Datenstrukturen in C: Shellsort</a> – Lern- und Lehrmaterialien</div>

<ul><li><a rel="nofollow" class="external text" href="https://hwlang.de/algorithmen/sortieren/shell/shell.htm">Shellsort Komplexität</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Einzelnachweise">Einzelnachweise</h2></div>

<li id="cite_note-1"><a href="#cite_ref-1">↑</a> Robert Sedgewick, Algorithmen, 3. unveränderter Nachdruck 1994, ISBN 3-89319-402-9, S. 136

</li>

<li id="cite_note-2"><a href="#cite_ref-2">↑</a> <a rel="nofollow" class="external text" href="https://www.researchgate.net/publication/3513516_Improved_lower_bounds_for_Shellsort">Conference Paper: Improved lower bounds for Shellsort.</a> In: ResearchGate. ResearchGate, November 1992, abgerufen am 29. März 2023 (englisch).<span style="display: none;" class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Adc&rfr_id=info%3Asid%2Fde.wikipedia.org%3AShellsort&rft.title=Conference+Paper%3A+Improved+lower+bounds+for+Shellsort&rft.description=Conference+Paper%3A+Improved+lower+bounds+for+Shellsort&rft.identifier=https%3A%2F%2Fwww.researchgate.net%2Fpublication%2F3513516_Improved_lower_bounds_for_Shellsort&rft.publisher=ResearchGate&rft.date=1992-11&rft.language=en">

</li>

<li id="cite_note-3"><a href="#cite_ref-3">↑</a> Robert Sedgewick, Algorithmen, 3. unveränderter Nachdruck 1994, ISBN 3-89319-402-9, S. 136

</li>

</ol></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2025-10-18" href="https://de.wikipedia.org/wiki/?title=Shellsort&oldid=260695869">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>